/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

// 执行用时：744 ms, 在所有 C 提交中击败了17.52% 的用户
// 内存消耗：52.8 MB, 在所有 C 提交中击败了62.77% 的用户
void find_max_min(int arr[], int n, int *max, int *min) {
    int min_idx = 0, max_idx = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] < arr[min_idx]) min_idx = i;
        if (arr[i] > arr[max_idx]) max_idx = i;
    }
    *max = arr[max_idx];
    *min = arr[min_idx];
}

// void build_seg_tree(int arr[], int tree[], int node, int start, int end) {
//     if (start == end) 
//         tree[node] = ;  // 元素存在则为1, 怎么判断存在?
//     else {    // 递归统计数量
//         // int mid = (start + end) / 2; // 如果是负数会有问题，，，
//         int mid = start + (end - start) / 2;
//         int left_node  = 2 * node + 1;
//         int right_node = 2 * node + 2; 
//         build_seg_tree(arr, tree, left_node, start, mid);
//         build_seg_tree(arr, tree, right_node, mid+1, end); 
//         tree[node] = tree[left_node] + tree[right_node];
//     }
// }

// 添加一个元素到线段树，元素所属的区间，都加1  //元素添加与线段树节点个数无关，线段树只负责记录元素个数
void insert_val(int tree[], int len, int node, int start, int end, int val) {
    if (val >= start && val <= end) {
        tree[node]++;
        
        int mid = start + (end - start) / 2;
        int left_node  = 2 * node + 1;
        int right_node = 2 * node + 2; 
        if (left_node < len) // 左孩子存在
            insert_val(tree, len, left_node, start, mid, val);
        if (right_node < len) // 右孩子存在
            insert_val(tree, len, right_node, mid+1, end, val);
    }
}

void delete_val(int tree[], int len, int node, int start, int end, int val) {
    if (val >= start && val <= end) {
        tree[node]--;
        
        int mid = start + (end - start) / 2;
        int left_node  = 2 * node + 1;
        int right_node = 2 * node + 2; 
        if (left_node < len)
            delete_val(tree, len, left_node, start, mid, val);
        if (right_node < len)
            delete_val(tree, len, right_node, mid+1, end, val);
    }
}



// 查询落在[L, R]区间中的元素的个数
int query_count(int tree[], int node, int start, int end, int L, int R) {
    if (L > end || R < start)   // 没有落在区间
        return 0;
    else if (start == end || L <= start && end <= R)    // 包含的区间
        return tree[node];
    else {
        int mid = start + (end - start) / 2;
        int left_node  = 2 * node + 1;
        int right_node = 2 * node + 2; 

        int left_count = query_count(tree, left_node, start, mid, L, R);
        int right_count = query_count(tree, right_node, mid+1, end, L, R);
        return (left_count + right_count);
    }
}

// 最接近且大于val的2次幂
int closest_2power_number(int val) {
    int number = 2;
    while (number < val) number <<= 1;
    return number;
}

// 如果数据太离散, 用线段树会浪费不少空间

// 用顺序存储的方式怎么做?
// 叶子节点应该有numsSize个, 要构造成满二叉树, 则tree[]长度要为2*x(最接近且大于numsSize的2次幂) - 1
// tree[0] 表示落在[min, max]区间的元素个数, tree[1]表示落在[min, mid]区间的元素个数
int* countSmaller(int* nums, int numsSize, int* returnSize){
    int min, max;
    find_max_min(nums, numsSize, &max, &min);
    // printf("min:%d max:%d\n", min, max);

    int number = closest_2power_number(max-min+1);   //[min, max]
    int tree_size = 2 * number - 1;

    int tree[tree_size];    
    memset(tree, 0, sizeof(int)*tree_size);   
    // printf("tree_size:%d\t 区间: [%d, %d]\n", tree_size, min, max);

    for (int i = 0; i < numsSize; i++) {
        insert_val(tree, tree_size, 0, min, max, nums[i]);
    }
    // for (int i = 0; i < numsSize; i++) 
    //     printf("落在区间[%d, %d]的元素个数：%d\n", min, nums[i], query_count(tree, 0, min, max, min, nums[i]));
    // printf("\n");

    // 查询右侧比nums[i]小的元素个数 
    int *res = calloc(numsSize, sizeof(int));
    for (int i = 0; i < numsSize; i++) {
        res[i] = query_count(tree, 0, min, max, min, nums[i]-1); //查询落在[min, nums[i])区间的元素个数
        delete_val(tree, tree_size, 0, min, max, nums[i]); //nums[i]已经用过，不能再考虑
    }

    *returnSize = numsSize;
    return res; 
}